import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Demo02 {
//    1. 二叉树的前序遍历
//    给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
//    示例 1：
//    输入：root = [1,null,2,3]
//    输出：[1,2,3]
//    示例 2：
//    输入：root = []
//    输出：[]
//    示例 3：
//    输入：root = [1]
//    输出：[1]
//    示例 4：
//    输入：root = [1,2]
//    输出：[1,2]
//    示例 5：
//    输入：root = [1,null,2]
//    输出：[1,2]

//    public static void preOrderNor(TreeNode root){
//        if(root==null){
//            return;
//        }
//        TreeNode cur=root;
//        Deque<TreeNode> stack=new ArrayDeque<>();
//        while (cur!=null||!stack.isEmpty()){
//            while (cur!=null){
//                stack.push(cur);
//                System.out.println(cur.val+" ");
//                cur=cur.left;
//            }
//            TreeNode top=stack.pop();
//            cur=top.right;
//        }
//        System.out.println();
//    }



//    2. 二叉树的中序遍历
//    给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
//    示例 1：
//    输入：root = [1,null,2,3]
//    输出：[1,3,2]
//    示例 2：
//    输入：root = []
//    输出：[]
//    示例 3：
//    输入：root = [1]
//    输出：[1]

//    public static void inOrderNor(TreeNode root){
//        if(root==null){
//            return;
//        }
//        TreeNode cur=root;
//        Deque<TreeNode> stack=new ArrayDeque<>();
//        while(cur!=null||!stack.isEmpty()){
//            while (cur!=null){
//                stack.push(cur);
//                cur=cur.left;
//            }
//            TreeNode top=stack.pop();
//            System.out.println(top.val+" ");
//            cur=top.right;
//        }
//        System.out.println();
//    }




//    3. 二叉树的后序遍历
//    给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
//    示例 1：
//    输入：root = [1,null,2,3]
//    输出：[3,2,1]
//    示例 2：
//    输入：root = []
//    输出：[]
//    示例 3：
//    输入：root = [1]
//    输出：[1]

    public static void postOrderNor(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode cur=root;
        TreeNode prev=null;
        Deque<TreeNode> stack=new ArrayDeque<>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||top.right==prev){
                System.out.println(top.val+" ");
                stack.pop();
                prev=top;
            }else{
                cur=top.right;
            }
        }
        System.out.println();
    }


}






